#include "union_find.h"

// 初始化, 各自为一组
union_find::union_find(int quantity)
{
    m_parent_num = new int[quantity + 1];
    m_quantity = quantity;

    for (int i = 0; i <= quantity; ++i)
    {
        m_parent_num[i] = 0;
    }
}

union_find::~union_find()
{
    delete[] m_parent_num;
}

void union_find::unite(int group_sign1, int group_sign2)
{
    // if (group_sign1 <= 0 || group_sign1 > m_quantity || group_sign2 <= 0 || group_sign2 > m_quantity)
    // {
    //     // group sign error
    //     return;
    // }

    // // 检查一下是否会自己合并自己
    // if (group_sign1 == group_sign2)
    // {
    //     return;
    // }
    // else 
    // {
    //     // 直接把group_sign2接到group_sign1上 nonono 要把group_sign2的根接到group_sign1
    //     // 这就是把根接上的
    //     m_parent_num[group_sign2] = group_sign1;
    // }
    m_parent_num[group_sign2] = group_sign1; //不是这里的问题
}

// int union_find::find(int element_num)
// {
//     // 找到根元素
//     int self = element_num;
//     int parent = m_parent_num[element_num];
//     while (parent != 0)
//     {
//         self = parent;
//         parent = m_parent_num[parent];
//     }

//     return self;
// }

int union_find::find(int element_num) // 降低高度后, 消除了超时
{
    int root = element_num;
	while (m_parent_num[root] != 0) 
    {
        //找根 
		root = m_parent_num[root];
	}
	while (element_num != root) 
    {
        //将所有的点都连到根上，降低高度 
		int t = m_parent_num[element_num];
		m_parent_num[element_num] = root;
		element_num = t;
    }

    return root;
}